In this chapter, we investigate the potential of green navigation services based on experiences with an implemented green navigation service, called GreenGPS, that gives drivers the most fuel-efficient route for their vehicle as opposed to the shortest or fastest route. The material in this chapter is largely based on the original GreenGPS manuscript, published in Mobisys 2010 [16].