Mea culpa, I didn't want to steal the thunder from the great guys at Opera. From my end user perspective I only remember Opera supporting the <video> tag in a version which was released almost a year after Firefox 3.5 [1].
[1] http://dev.opera.com/articles/view/introduction-html5-video/
I worked on the Mozilla HTML video implementation. Opera came up with the original proposal and presented a first experimental implementation. We started implementing this to be compatible.
Apple then presented their much more complicated proposal which was integrated with the Opera one and became HTML 5 video, along with feedback from other implementers, including Mozilla.
So it's a bit more complicated than "Mozilla implemented first".