While the advent of ICT has produced mixed results for the travel agency businesses, one of the differentiating factors has been how different businesses have strategically responded to the new business environment. In view of the threats and opportunities presented by ICTs to the travel sector, this study sought to examine the different strategies adopted by the travel agents in Kenya in an effort to strategically reposition themselves. The survey was conducted among 55 travel agency operators in Nairobi, Kenya using a semi-structured questionnaire. The study found out that travel agents in Kenya have adopted a number of ICT innovations to stay afloat. Among the most significant strategic innovations has been the travel agent’s increased client focus as opposed to focus on service providers. This has seen the travel agents forge close relationships with their clients through both online and offline approaches. It is imperative to note that investing in customers and developing a strong relationship marketing strategy to attract and retain them is the new area of competitiveness today. This study thus provides a new perspective to the strategic response of travel agencies to macro-environmental threats and opportunities presented by current developments in ICTs.