"es_ES" is a language + country. You must specify each part separately.

The constructors for Locale are:

• Locale(String language)
  Construct a locale from a language code.
• Locale(String language, String country)
  Construct a locale from language, country.
• Locale(String language, String country, String variant)
  Construct a locale from language, country, variant.

You want new Locale("es", "ES"); to get the Locale that goes with es_ES.

However, it would be better to use Locale.forLanguageTag("es-ES"), using the well-formed IETF BCP 47 language tag es-ES (with - instead of _), since that method can return a cached Locale, instead of always creating a new one.

tl;dr

String output =     ZonedDateTime.now ( ZoneId.of ( "Europe/Madrid" ) )    .format (         DateTimeFormatter.ofLocalizedDate ( FormatStyle.FULL )                         .withLocale ( new Locale ( "es" , "ES" ) )     );

martes 12 de julio de 2016

Details

The accepted Answer by Affe is correct. You were incorrectly constructing a Locale object.

java.time

The Question and Answer both use old outmoded classes now supplanted by the java.time framework built into Java 8 and later. These classes supplant the old troublesome date-time classes such as java.util.Date. See Oracle Tutorial. Much of the java.time functionality is back-ported to Java 6 & 7 in ThreeTen-Backport and further adapted to Android in ThreeTenABP.

These classes include the DateTimeFormatter to control the format of text when generating a String from your date-time value. You can specify an explicit formatting pattern. But why bother? Let the class automatically localize the format to the human language and cultural norms of a specific Locale.

For example, get the current moment in Madrid regional time zone.

ZoneId zoneId = ZoneId.of( "Europe/Madrid" );ZonedDateTime zdt = ZonedDateTime.now( zoneId );// example: 2016-07-12T01:43:09.231+02:00[Europe/Madrid] 

Instantiate a formatter to generate a String to represent that date-time value. Specify the length of the text via FormatStyle (full, long, medium, short).

DateTimeFormatter formatter = DateTimeFormatter.ofLocalizedDate ( FormatStyle.FULL );

Apply a Locale to substitute for the JVM’s current default Locale assigned to the formatter.

Locale locale = new Locale ( "es" , "ES" );formatter = formatter.withLocale ( locale );

Use the formatter to generate a String object.

String output = zdt.format ( formatter );// example: martes 12 de julio de 2016

Dump to console.

System.out.println ( "zdt: " + zdt + " with locale: " + locale + " | output: " + output );

zdt: 2016-07-12T01:43:09.231+02:00[Europe/Madrid] with locale: es_ES | output: martes 12 de julio de 2016

Java 8

LocalDate today = LocalDate.now();String day = today.getDayOfWeek().getDisplayName(TextStyle.FULL, new Locale("es","ES")));

Also works for month.