You need to contact the Standesamt in Konstanz and request her birth certificate. Just provide her birth date and parents names (if known).
Here is their e-mail: firstname.lastname@example.org
and here is their webpage: http://www.konstanz.de/rathaus/00707/01001/01006/index.html
If you know where she was married in Germany, then you can contact the Standesamt for that town too and provide the date of marriage.
It should provide you parents names and then you can further request their marriage or birth and even death records. Once you have reached a time period before 1874 you can start looking in the church records.