Plus jeune conseillère municipale de Metz en 1983, elle est, en 1988, élue à une très forte majorité conseillère générale de la Moselle par le canton de Metz 3, le plus important du département. Elle a depuis lors été réélue en 1994 avec 60 % des voix, puis en 2001 avec 70 % des suffrages.
Élue adjointe au maire en 1987, puis première adjointe en 1995, Nathalie Griesbeck a, jusqu’au terme de l’année 2004, eu en charge plus particulièrement les deux délégations des finances et du développement économique, avec notamment la responsabilité du technopole de Metz et des zones de développement. Elle est également parvenue à redresser l’OPAC de Metz, dont elle a assuré la présidence de 1995 à 2001.
Le , Nathalie Griesbeck a annoncé sa candidature à la mairie de Metz dans le cadre des élections municipales des 9 et , où elle obtient 14,69 % des suffrages exprimés (5 289 voix)[2].
Conseil général de la Moselle
Présidente de l’association départementale du troisième âge, plus connue sous le nom d’Hôtel de Gournay, et dont l’action s’étend à l’ensemble du département de la Moselle. Rapporteure générale du budget du département de la Moselle de 1998 à 2001, elle y préside, de 2001 à 2004, la commission des affaires sociales, scolaires universitaires et de recherche.
À la suite des élections cantonales de , elle a été élue vice-présidente du Conseil général de la Moselle et présidente de la commission Affaires sociales, scolaires, universitaires et de recherche.
Parlement européen
Lors des élections européennes de 2004, où elle a conduit la liste UDF pour la circonscription interrégionale du Grand Est, qui compte plus de huit millions d’habitants et regroupe dix-huit départements en cinq régions —Alsace, Bourgogne, Champagne-Ardenne, Franche-Comté et Lorraine— elle a été élue parlementaire européen avec un score très favorable, notamment en Moselle et plus particulièrement à Metz (plus de 22%) où elle arrive les deux fois largement en tête de la droite parlementaire, en obtenant 10 points de plus que le candidat de l’UMP, tant et si bien que sa liste a dépassé dans l’ensemble du Grand Est la moyenne nationale de l’UDF et qu’elle est parvenue à faire élire également un second représentant au Parlement européen.
Appelée à choisir entre les différents mandats, elle décide, au terme de l’année 2004, de privilégier sa fonction de députée européenne ainsi que son mandat de conseillère générale de la Moselle, où elle est désormais chargée du logement social. À ce titre, elle vient d’être élue vice-présidente de l’Union des conseillers généraux de France.
À partir de 2009, elle siège au sein des commissions LIBE (Libertés civiles, Justice et Affaires intérieures) et TRAN (Transports et tourisme). Le , le Parlement européen se prononce à une très forte majorité (577 voix pour, 48 contre) en faveur du rapport, conduit par elle, concernant l'application du respect des droits de la défense et de la présomption d'innocence dans toute l’Europe[4].
Elle emploie à mi-temps comme assistante parlementaire la standardiste du parti, et ce pendant cinq ans. Il s'agit d'un emploi fictif selon France Info[5].