La prima volta del Milan in Coppa UEFA risale alla stagione 1971/72 e corrisponde alla miglior performance di sempre dei rossoneri nella competizione insieme a quella del 2001/02. La squadra di Nereo Rocco inizia il suo cammino affrontando nei Trentaduesimi di finale i ciprioti del Digenís Akrítas Mórphou (D.A.M.). I rossoneri vincono facilmente l'andata a San Siro per 4-0 (doppietta di Villa II e goal di Magherini e Golin) per poi imporsi al ritorno per 0-3 in una partita che su richiesta degli avversari si disputa a Trieste (a segno ancora Villa II con una doppietta e Rivera, al debutto nella competizione).
Nei sedicesimi si alza l'asticella: avversari del Diavolo sono infatti i tedeschi occidentali dell'Hertha Berlino. A San Siro i rossoneri vincono 4-2. Dopo il vantaggio avversario al 15', Prati firma l'1-1 al 39', ma nella ripresa sono ancora gli ospiti a portarsi avanti al 51'. Serve così una grande prova nell'ultima mezz'ora per raddrizzare il discorso qualificazione: Romeo Benetti (62'), Biasiolo (64') e ancora Prati (84) ristabiliscono i rapporti di forza. Tutto però si decide nel match di ritorno. Il Milan soccombe 2-1, ma il vantaggio iniziale di Albertino Bigon (12') porta la formazione rossonera agli ottavi.
L'avversario è la formazione scozzese del Dundee FC. Come da tradizione, la squadra di Rocco ipoteca la qualificazione nella sfida di andata a San Siro. Gli scozzesi vengono travolti 3-0 (Rivera, autorete Stewart e Romeo Benetti in goal) e nel match di ritorno basterà contenere i danni. Il copione classico si ripete, il Milan cade 2-0 al Dens Park ma il risultato dell'andata lo qualifica ai quarti di finale.
L'urna abbina i rossoneri ai belgi del Lierse. Nella gara di andata in casa il Milan vince 2-0 (Rivera su rigore e Bigon) e poi pareggia 1-1 nel ritorno in terra belga (vantaggio a inizio ripresa di Villa II, pari nel finale su rigore dei padroni di casa). Ancora una volta la strategia paga e il Diavolo avanza in semifinale.
La squadra di Rocco, che in campionato lotta con la Juventus per lo Scudetto, è convinta di poter arrivare in fondo. Ma nelle semifinali trova un duro ostacolo come gli inglesi del Tottenham. Nell'andata del Whiter Hart Lane, a Londra, gli Spurs si impongono 2-1. Dopo il vantaggio di Benetti, Perryman pareggia e nella ripresa al 65' si ripete con il punto del 2-1.
Per qualificarsi in finale il Diavolo deve ribaltarla a San Siro, ma la squadra arriva all'appuntamento piuttosto stanca e non va oltre l'1-1: inglesi avanti in avvio con Mullery, Rivera pareggia nella ripresa dal dischetto e tuttavia deve fare i conti con l'amara eliminazione. Il Tottenham solleverà poi il trofeo battendo in finale i connazionali del Wolverhampton, mentre i rossoneri, secondi in campionato, vinceranno la Coppa Italia.
Negli anni Settanta il Milan disputa la Coppa UEFA altre tre volte. Nel 1975/76 i lombardi, guidati da Gustavo Giagnoni, eliminati Everton, Athlone Town e Spartak Mosca, cadono nei quarti di finale ad opera del Bruges. In panchina c'è Trapattoni, con Rocco come Direttore tecnico, i rossoneri perdono 2-0 allo Stadio Olimpico di Bruges e al ritorno sono beffati nel secondo tempo. In vantaggio 2-0 con i goal di Bigon (32') e Chiarugi (66'), sono puniti da una rete di Hinderyckx al 74' e vengono eliminati.
La terza apparizione del Milan in Coppa UEFA arriva l'anno seguente: nel 1976/77 i rossoneri si fermano agli ottavi di finale. Eliminati i rumeni della Dinamo Bucarest e i bulgari dell'Akademik Sofia, la squadra di Pippo Marchioro esce con le ossa rotte dall'andata a "La Catedral" di Bilbao. Nel clima fortemente ostile del vecchio San Mamés, i rossoneri sono travolti 4-1: in vantaggio con una rete di Fabio Capello, subiscono il pareggio su rigore prima dell'intervallo e altri 3 goal nella ripresa. Nel ritorno a San Siro si impongono 3-1 (doppietta di Calloni e rete di Biasiolo) ma sono nuovamente eliminati.
Non va meglio nel 1978/79, quando gli uomini di Liedholm, eliminati i cecoslovacchi del Lokomotiva Kosice e i bulgari del Levski Spartak, escono per mano degli inglesi del Manchester City. La prima gara a San Siro è rinviata di un giorno per nebbia, e nel recupero i rossoneri non vanno oltre il 2-2 (doppietta di Bigon nel secondo tempo), per poi perdere nettamente nel ritorno a Maine Road (3-0 per i Citizens).