Sixteen physicochemical parameters including four major and ten trace metals were analyzed for seven top soil and six top stream sediment samples collected around the vicinity of cement factory in Mekelle, Ethiopia. Water and aqua regia extraction techniques were deployed to determine the water soluble and near total concentration of the metals in the samples. Water extraction results verified the magnitude of loading of the metals from anthropogenic sources. The mean values of the water soluble metals are found to exceed the reference values except for Ca and Zn in both lithogenic media indicating the severity of pollution. Spatial distribution of the metals suggested that cement factory dust and traffic emissions represent the most important pollutant sources for the investigated area.  The mean proportion of the major and trace metals in the water soluble phase of soil can be put on a descending order as: Mg (57.76%) > Fe > Ca > K > Na > Mn (3.77%) and Mo (53.17%) > Cu > Co > As > Ni > Zn > Pb > Cr (5.02%) respectively. The order of major metals is almost reverse in the case of the stream sediment with slight difference in the order of the trace metals. Factor analysis has revealed that the first factor represents the contribution of metals (Mn, Cr, As, Co, Zn, Na, K, Cu, Pb and Ni) from local anthropogenic activities, whereas the second factor represents the contribution of metals (Na, Fe, Cu, Pb, Ni, Ca, As, Co, Zn and Mo) from both lithogenic and anthropogenic origins. Third factor consists of Ca, Mo, Mg, and Fe from geogenic source of the local geology. It is spatially evident that the cement dust emission has an impact on the soil’s Cr, Co, Mo and Ni content which drastically decreases downstream. The spatial pattern of Cu, Pb, As, Zn and Co shows significant association with the cement dust and loadings from the traffic movement on the road.