The first parish in Toronto was St. Paul's, established in 1822. The first red brick structure (described as "Gothic" but I haven't yet found a picture of it) was opened in 1824. At the time it was the only Catholic church between Kingston and Windsor. In 1845 Toronto's first bishop Michael Power (who chose St. Michael the Archangel as the patron of the diocese) laid the cornerstone for the Cathedral. He never saw the building completed. He died October 1, 1847, after he had contracted Typhus from tending the flood of refugees from the Irish potato famine who came Toronto in the summer of '47.
Incidentally, many of those Irish immigrants died of the disease, and were buried in the graveyard at St Paul's. Around the turn of the century, the gravestones were removed and demolished, and the graveyard was turned into a schoolyard, among other things. The bodies are still there. Occasionally someone digging in the area will find one.
The next oldest church still standing is St. Basil's, which is a miniature copy of the cathedral, built in 1855. Our Lady of Lourdes comes from around 1884, St Mary's was built in 1885, and the spire was added 1904. The current St Paul's was built 1887, and is a strong contender for Toronto's most beautiful church. According to Wikipedia, St. Patrick's, built in 1908, is Toronto's fifth oldest Church. Wikipedia must not be including the Cathedral. St. Patrick's is also one of the few churches that has a Gregorian Schola. The really odd thing about St. Patrick's is that is the fifth oldest Church in the diocese that is named after St. Patrick. In a diocese which was founded mostly by the Irish, I would have expected his name to turn up much earlier than this.
So the oldest Church in Toronto would be the original St. Paul's... if it still stood. Instead it was demolished around the same time as the cemetery, as it had fallen into disuse after the construction of the new building. Which means the oldest Catholic Church in Toronto is... the Cathedral itself, unless you don't count the Cathedral as a Church, which Wikipedia does not, in which case the oldest church in Toronto is St Basil's... the cathedral in miniature.
Most of this I got from Wikipedia and the archdiocese. Some of the dates may be a little off. St. Patrick's and St. Mary's both figure prominently in the Jubilee Riots of 1875, which may mean the dates are either wrong, or there were other churches on those grounds at the time which were demolished for larger and more grand buildings. This would clear up the St Patrick problem somewhat. It also seems to me that there are other churches from the 19th century still around, unfortunately few have their own websites, so I'm having some trouble confirming this.
A few more notes. I said Bishop Power never saw the Cathedral completed. Technically, neither has anyone else. It was supposed to be a full cruciform church, but the transepts were never completed. In 1850, Toronto's second bishop, Bishop Armand François Marie de Charbonnel, P.S.S, was installed. Shortly afterwards he paid off much of the debt on the Cathedral out of his own personal estate. He also added the three great east windows and the Stations of Cross, all imported from France.
The Cathedral fell onto hard times for a while, but the building is now being restored. This creates problems which are exacerbated by the need to shut down the renovations several times a day for Mass, and also by the tendency of contractors to treat the Cathedral as an all you can eat steak buffet. Even so, it is a beautiful building and can be so again.
One last note, the current pastor at St Paul's basilica has one of the most appropriate names for a priest ever. He is Rev. Monsignor Bradley H. Massman.
Update: David sent this note on Haloscan, answering the St. Patrick's question:
Actually, the "original" St. Patrick's dates from 1867. It still stands on St. Patrick Street just north of Dundas Street directly behind the east facing St. Patrick's on McCaul Street. It is known as Our Lady of Mount Carmel and is a Chinese ethnic parish. After the "new" St. Patrick's was built (where my father was baptised and my parents married) the "old" was renamed Our Lady of Mount Carmel and given over to the Italian community. It recently underwent a quasi-restoration but not a full historical restoration.
So the the original is still around. I wonder why I found no note of it. Thanks, David.
I've done some more poking around. Most of the older churches had earlier wooden structures which were replaced as soon as the parish had the money, but it would take more digging to find dates for that. I wonder what happened in the 1880's that four parishes expanded in a big way. That could be a post for another time.