This paper discusses the effect of Information and Communication Technologies (ICTs) on the labor productivity of the service sector in Palestine. Using cross-sectional data from 778 service firms, we find that using ICTs in service sector is positively and significantly affects labor productivity. Service sector firms that are less ICT-intensive are less productive when compared to more ICT-intensive firms. The use of E-commerce, mobile phones and more ICT-labor improves the labor productivity of service firms. The study also finds that Research and Development positively influences labor productivity only when it is complemented with more ICT labor. The colonial geographical segregation has significant effects on our results. For instance, the firms in Jerusalem are more productive and the firms in Gaza are less productive compared to the firms in the West Bank.