Édesapja, az ír klarinétos Thomas Sullivan a sandhursti Királyi Katonai Akadémia fúvószenekarának vezetője volt. Édesanyja olasz származású. Arthur a család második gyermeke. Zenei képességei korán megnyilvánultak, 1854-ben felvették a Chapel Royal énekkarába. 13 éves korában komponálta első művét. Mendelssohn-ösztöndíjat kapott, ennek révén 1856-ban bekerülhetett a londoni Királyi Zeneakadémiára. Lipcsében folytatta képzését. Tanulmányait a nagy feltűnést keltő, William Shakespeare Vihar-jához írott kísérőzenével zárta 1861-ben. A brit komolyzene nagy reménységét látták benne.

Kezdetben templomi orgonistaként működött. 1866-tól egykori alma matere, a Királyi Zeneakadémia zeneszerzéstanára. 1876 és '81 között a National Training School for Music igazgatója volt.

Zeneszerzőként pályáját „komoly” művekkel kezdte, pl. a Kenilworth c. kantátával (1864), a L'Île enchantée balett-tel, komponált dalokat, zongoradarabokat, szimfóniát, gordonkaversenyt, nyitányokat. Egyéb jelentős ilyen műve: Te Deum (1872), A vértanúk (1880). Ezek nem nyújtottak elegendő jövedelmet neki.

1866-ban fordult az operettek felé. Első két ilyen művét Sir Francis Cowley Bernard szövegére írta. 1871-ben kezdte együttműkődését W. S. Gilberttel. Első közös művük (Thespis. Extravaganza két felvonásban) szolíd sikert aratott, de a bemutató színház vezetője további darabokat rendelt tőlük. Egyre nagyobb sikereket értek el, ontották az operetteket. 1881-től a Richard D'Oyly Carte-vezette Savoy Theatre mutatta be műveiket. 1889-ben a színház új szőnyege miatt összeveszett a szerzőpáros, és hosszú szünet után már csak két közös művet alkottak.

Az 1880-as években megpróbált más librettistákkal ismét komoly darabokat írni, de ezek nem váltak maradandóvá (The Golden Legend [1886], Ivanhoe [ötfelvonásos opera Sir Walter Scott nyomán, 1891]).

Viktória királynő többféleképpen kitüntette (lovagi cím 1883-ban), azonfelül a királyi zeneakadémia elnöke lett.

Sullivan összesen mintegy háromszáz művet alkotott a legkülönbözőbb műfajokban, de mára a Gilbert librettőira írt operettjei kivételével ezek feledésbe merültek. Az operbase honlap mutatja, hogy napjainkban a legtöbbet játszott operettjei a Mikado és a The Pirates of Penzance (Kalózkaland) maradtak, emellett többször is repertoárra került a H M S Pinafore és a Trial by Jury, valamint más művei is a világ számos országában, főként angol nyelvterületen.