When we start a sentence with the word before, we generally follow it with the past tense (in constructions such as yours).
Before I started....
Before he went ....
Before she sang....
This is true also for since.
So you would write:
Before I started AT (the) university....
If you wrote: Before I started the university it would mean that you were the founder of the university.
The second half of your sentence is correct:
Before I started at university, I worked as a waitress in a cafe.
Another way to say it is:
Before starting at the university, .....
In some circumstances, an option is to use the PAST PERFECT in the second clause. For example:
Before I started at university, I had worked as a waitress in a cafe and for some years after that I supported myself by walking people's dogs.
This makes it clear that the order of events is waitressing, followed by dog-walking, followed by university studies.