Der Ursprung des heutigen Unternehmens liegt im Jahre 1896, als der Spanier Federico Paternina in Ollauri im Rioja-Bereich drei Bodegas kaufte. Darunter war die bereits aus dem 16. Jahrhundert stammende Conde de los Andes. Im Jahre 1920 erwarb Paternina eine Genossenschaft in Haro und erweiterte dadurch seine Produktion beträchtlich. Ab den 1940er-Jahren wurde damit begonnen, die Weine weltweit zu exportieren. In den 1960er-Jahren geriet das Unternehmen zunehmend in Schwierigkeiten und wurde von der Firma Rumasa (mit dem Eigentümer Jose Marea Ruiz Mateos) erworben. Aber die Probleme von Paternina und auch des neuen Eigentümers wurden noch größer. Anfang der 1980er-Jahre wurde dann die schwer verschuldete Firma Rumasa und damit auch Paternina von der spanischen Regierung übernommen.
Bei einer Auktion wurde Paternina von Marcos Eguizábal Ramirez im Jahre 1985 um einen einzigen Peseta erworben. Der Anfang war hart, so mussten zum Beispiel 40.000 Kisten qualitativ schlechten Weines vernichtet werden. Im Jahre 1990 wurde eine neue Kellerei in Haro in Betrieb genommen. Bis Mitte der 1990er-Jahre wurde durch gute Produkte wieder der alte Ruf hergestellt. Inzwischen war Marcos Sohn Carlos Eguizábal im Unternehmen tätig. Schließlich ging Paternina 1998 an die Börse. Zum Unternehmen gehört übrigens auch das Weingut Bodegas Franco Españolas. Schon im Jahre 1994 wurde die Firma „Bodegas Internacionales“ in Jerez gekauft, in deren Besitz eine Reihe von traditionellen Sherrymarken wie Bertola, Díez Hermanos, Marqués de Mérito, Bertola und José Pemartín y Cia war. Paternina begann nun verstärkt, Sherry und Brandy de Jerez zu produzieren und entwickelte sich zu einem führenden Hersteller. Die Sherry-Produktion später wieder verkauft.
Die neue Rioja-Kellerei liegt in der Stadt Haro im Zentrum des Rioja-Subbereiches Rioja Alta. Die eigenen Weinberge umfassen 100 Hektar Rebfläche, aber es werden auch Trauben in großem Umfang von Genossenschaften und Winzern angekauft. Für den Ausbau der Weine stehen 50.000 Barriquefässer zur Verfügung. Die größte Produktions-Menge machen die Crianzas „Banda Azul“, „Banda Rojo“ und „Banda Dorada“ aus (70 bis 80% Tempranillo, 10 bis 20% Garnacha Tinta, 5 bis 10% Mazuelo, bis 5% Graciano). Die Spitzenprodukte sind der Reserva „Viña Vial“, sowie die Gran Reservas „Federico Paternina“ (65% Tempranillo, 15% Garnacha Tinta, 10% Graciano, 10 % Mazuelo) und „Conde de los Andes“ (80% Tempranillo, 10% Garnacha Tinta und 10% Mazuelo). Eine neue Bodega in der Gemeinde Quintana del Pidio bei Pesquera de Duero in der Region Kastilien-León wurde im Jahre 2000 in Betrieb genommen. Die Weinberge in der DO Ribera del Duero umfassen 41 Hektar Rebfläche in Quintana del Pidio, Gumiel de Mercado und in Gumiel de Izán. Eine Erweiterung auf einen Umfang von 100 Hektar ist geplant. Die Weine werden unter dem Label Marqués de Valparaiso seit dem Jahrgang 2004 vermarktet.
