As the number of sites on the Web increased in the mid-to-late 90s, search engines started appearing to help people find information quickly. Search engines developed business models to finance their services, such as pay per click programs offered by Open Text in 1996 and then Goto.com in 1998. Goto.com later changed its name to Overture in 2001, and was purchased by Yahoo! in 2003, and now offers paid search opportunities for advertisers through Yahoo! Search Marketing. Google also began to offer advertisements on search results pages in 2000 through the Google AdWords program. By 2007, pay-per-click programs proved to be primary money-makers for search engines. In a market dominated by Google, in 2009 Yahoo! and Microsoft announced the intention to forge an alliance. The Yahoo! & Microsoft Search Alliance eventually received approval from regulators in the US and Europe in February 2010.

Search engine optimization consultants expanded their offerings to help businesses learn about and use the advertising opportunities offered by search engines, and new agencies focusing primarily upon marketing and advertising through search engines emerged. The term "Search Engine Marketing" was proposed by Danny Sullivan in 2001to cover the spectrum of activities involved in performing SEO, managing paid listings at the search engines, submitting sites to directories, and developing online marketing strategies for businesses, organizations, and individuals.

Paid search advertising has not been without controversy, and the issue of how search engines present advertising on their search result pages has been the target of a series of studies and reportsby Consumer Reports WebWatch. The Federal Trade Commission (FTC) also issued a letterin 2002 about the importance of disclosure of paid advertising on search engines, in response to a complaint from Commercial Alert, a consumer advocacy group with ties to Ralph Nader.

Another ethical controversy associated with search marketing has been the issue of trademark infringement. The debate as to whether third parties should have the right to bid on their competitors' brand names has been underway for years. In 2009 Google changed their policy, which formerly prohibited these tactics, allowing 3rd parties to bid on branded terms as long as their landing page in fact provides information on the trademarked term.Though the policy has been changed this continues to be a source of heated debate.

At the end of February 2011 many started to see that Google has started to penalize companies that are buying links for the purpose of passing off the rank. SEM has however nothing to do with link buying and focuses on organic SEO and PPC management.

SEM is the wider discipline that incorporates SEO. SEM includes both paid Search results (Adwords) and organic search results (SEO). SEM uses Adwords,pay per call (particularly beneficial for local providers as it enables potential consumers to get in touch directly to a company with one click), article submissions, advertising and making sure SEO has been done. A keyword analysis is performed for both SEO and SEM, but not necessarily at the same time. SEM and SEO both need to be monitored and updated frequently to reflect changing usage.

In some contexts the term SEM is used exclusively to mean Pay per click advertising, particularly in the commercial advertising and marketing communities which have a vested interest in this narrow definition. Such usage excludes the wider search marketing community that is engaged in other forms of SEM such as Search Engine Optimization and Search Retargeting.

Another part of SEM is Social Media Marketing (SMM). SMM is a type of marketing that involves exploiting social media to influence consumers that one company’s products and/or services are valuable. Some of the latest theoretical advances include Search Engine Marketing Management (SEMM). SEMM relates to activities including SEO but focuses on return on investment (ROI) management instead of relevant traffic building (as is the case of mainstream SEO). SEMM also integrates organic SEO, trying to achieve top ranking without using paid means of achieving top in search engines, and PayPerClick SEO. For example some of the attention is placed on the web page layout design and how content and information is displayed to the website visitor.

There are four categories of tools to help you optimize websites.

1. Keyword research and analysis: (a) Make sure the site can be indexed in the search engines; (b) find the most relevant and popular key terms and phrases for the site and its products; and (c) use those key phrases on the site in a way that will generate and convert traffic.

2. Website saturation and popularity: show how much presence a website has on search engines through the number of pages of the site that are indexed on each search engine (saturation) and how many times the site is linked to by other sites (popularity). Generally, the more Web presence you have, the easier it is for people to find your site. It requires your pages containing those keywords people are looking for and ensure that they rank high enough in search engine rankings. Most search engines include some form of link popularity in their ranking algorithms. The followings are major tools measuring various aspects of saturation and link popularity: Link Popularity, Top 10 Google Analysis, and Marketleap's Link Popularity and Search Engine Saturation.

3. Back end tools (including Web analytic tools and HTML validators): Web analytic tools can help you to understand what is happening to your website and measure your website's success. They range from simple traffic counters to tools that work with log files and to more sophisticated tools that are based on page tagging (putting JavaScript or an image on a page to track actions). These tools can deliver conversion-related information. There are three major tools used by EBSCO: (a) log file analyzing tool: WebTrends by NetiQ; (b) tag-based analytic programs WebSideStory's Hitbox; (c) transaction-based tool: TeaLeaf RealiTea. Validators check the invisible parts of websites, highlighting potential problems and many usability issues ensure your website meets W3C code standards. Try to use more than one HTML validator or spider simulator because each tests, highlights, and reports on slightly different aspects of your website.

4. Who Is tools: show you who owns and operates various webites, can provide valuable information relating to copyright and trademark issues. Useful tools include Who Is Source, ARIN. Read a competitor's source code to look for hidden clues, Use Web analytics tools to find out more about your customers, Use the source code and Who Is tools to research legal issues.