The Serie A outfit needed only a point against Ajax to progress from Group H, but Riccardo Montolivo's red card after only 22 minutes gave the Amsterdam club the initiative.
Italy midfielder Montolivo was shown a straight red card by referee Howard Webb for a late challenge on Christian Poulsen in a game dominated by the Dutch champions.
Poulsen had already hit the post with a header by then but, much to the delight of the under-pressure Allegri, gutsy Milan dug deep to thwart Ajax and ensure they are the only Italian club remaining in the competition.
He told Sky Sport Italia: "It was a long sigh of relief because this was an important achievement and it wasn't easy to play against Ajax with 10 men.
"The lads were very organized and only ran risks on a few crosses into the box, while Christian Abbiati did well on his saves. Mario Balotelli took the team upon his shoulders, earned free kicks and held the ball up, so he was crucial."
Allegri felt Montolivo was unfortunate to be given his marching orders, but remained pleased with the way his side kept Ajax at bay.
He added: "Montolivo's was a foul, but certainly not nasty, as he is not a nasty player. The referee made this decision on the suggestion of the assistant and it's a shame we had to play for over an hour with 10 men.
"From the touchline I couldn't see it. The replays show it was a hard foul, but not nasty. The lads didn't allow Ajax to get past them, didn’t allow spaces and I think we had a couple of dubious offsides against us too.
"It was tougher to go on the counter in the second half, as the more time went on, the more we could sense the finish line.
"Ah well, that's the way it went and we all lost a few kilos suffering on the touchline."