Fyrirtækið var stofnað árið 1983 og hét þá Control Video Corporation eða CVC. Fyrirtækið rak tölvunet fyrirAtari 2600-leikjatölvur sem hægt var að tengjast gegnummótald. Árið 1985 var nýtt fyrirtæki, Quantum Computer Services, stofnað á grunni CVC með netþjónustunaQuantum Link fyrirCommodore 64 og128. Árið 1988 komAppleLink fyrirApple Macintosh-tölvur og PC Link fyrirIBM PC-samhæfðar tölvur. Árið 1989 breytti fyrirtækið nafni sínu í America Online. Netleikir voru mikilvægur hluti af þjónustu fyrirtækisins. Árið 1993 bauð fyrirtækið upp áInternet-tengingu fyrir notendur. Það var þá orðið stærra en helstu keppinautar sínir,GEnie,Prodigy ogCompuServe. Árið 2000 sameinaðist AOL fjölmiðlarisanumTime Warner. Hluthafar AOL eignuðust 55% í nýja fyrirtækinu.
Eftir 2002 tók notendum AOL að fækka. Árið 2006 lokaði AOL síðasta þjónustuveri sínu í Bandaríkjunum. Árið 2009 var fyrirtækinu breytt í sjálfstætt netmiðlafyrirtæki með tekjur byggðar á auglýsingum. Það keypti vefmiðla á borð við The Huffington Post og hóf framleiðslu heimildaþátta. Árið 2015 keyptiVerizon AOL.