Background: Immunization remains one of the most important public health interventions and cost effective strategy to reduce both morbidity and mortality in children. World health organization estimated that if global immunization coverage rises to 90%, vaccines would prevent an additional two million deaths a year among children under five years. Nevertheless, global immunization coverage is still low, leading to two million deaths annually from vaccine preventable diseases. Assessment of immunization coverage provides evidences to evaluate progress in achieving programme objectives and in improving service delivery. Methods: A community based Cross sectional study was conducted in Tehulederie district North East Ethiopia from February 1 to 15, 2012. Multistage sampling technique was used to select study participants. Seven villages were selected by simple random sampling method. The sample size was allocated to the selected villages proportionally to population size. Logistic regression model was used to identify factors associated with full immunization coverage of children. Ethical clearance was obtained from college of Health sciences’ Ethical clearance committee, Jimma University. Results: All the villages were staffed with two Health Extension workers with ratio of 1:2591and 1:5180 population in rural and urban residences respectively. Five hundred fifty seven (87.2%) of the respondents were geographically accessible to the service and 96.8% of them accepted the service. 83.1% of children were fully immunized whereas 14.7% and 2.2% of the children were partially immunized and never vaccinated respectively. In the multivariate logistic regression analysis, children in rural areas were 8 times more likely to be fully immunized than children in urban residence (AOR= 8.01 95% CI: 3.78- 16.99) and children who had access for the service were 8 times more likely to be fully immunized than children who had no access for the service [AOR= 8.24 95% CI: 4.66- 14.59). Conclusions: Physical access to immunization was nearer to the national standards. The trend showed that the immunization coverage was tending to lower in later doses. Thus, it was recommended that attention should be given to awareness of mothers to complete doses in order to achieve full protection for their children.