When selecting an SEO agency, several factors should be taken into account. These include the agency's experience and proficiency, pricing and services provided, success rate, and communication and reporting methods. It's essential to look for an agency with a track record of enhancing their clients search engine rankings and delivering measurable results.