How to convert Milliseconds to "X mins, x seconds" in Java?

Use the java.util.concurrent.TimeUnit class:

String.format("%d min, %d sec", 
    TimeUnit.MILLISECONDS.toMinutes(millis),
    TimeUnit.MILLISECONDS.toSeconds(millis) - 
    TimeUnit.MINUTES.toSeconds(TimeUnit.MILLISECONDS.toMinutes(millis))
);

Note: TimeUnit is part of the Java 1.5 specification, but toMinutes was added as of Java 1.6.

To add a leading zero for values 0-9, just do:

String.format("%02d min, %02d sec", 
    TimeUnit.MILLISECONDS.toMinutes(millis),
    TimeUnit.MILLISECONDS.toSeconds(millis) - 
    TimeUnit.MINUTES.toSeconds(TimeUnit.MILLISECONDS.toMinutes(millis))
);

If TimeUnit or toMinutes are unsupported (such as on Android before API version 9), use the following equations:

int seconds = (int) (milliseconds / 1000) % 60 ;
int minutes = (int) ((milliseconds / (1000*60)) % 60);
int hours   = (int) ((milliseconds / (1000*60*60)) % 24);
//etc...

Based on @siddhadev's answer, I wrote a function which converts milliseconds to a formatted string:

   /**
     * Convert a millisecond duration to a string format
     * 
     * @param millis A duration to convert to a string form
     * @return A string of the form "X Days Y Hours Z Minutes A Seconds".
     */
    public static String getDurationBreakdown(long millis) {
        if(millis < 0) {
            throw new IllegalArgumentException("Duration must be greater than zero!");
        }

        long days = TimeUnit.MILLISECONDS.toDays(millis);
        millis -= TimeUnit.DAYS.toMillis(days);
        long hours = TimeUnit.MILLISECONDS.toHours(millis);
        millis -= TimeUnit.HOURS.toMillis(hours);
        long minutes = TimeUnit.MILLISECONDS.toMinutes(millis);
        millis -= TimeUnit.MINUTES.toMillis(minutes);
        long seconds = TimeUnit.MILLISECONDS.toSeconds(millis);

        StringBuilder sb = new StringBuilder(64);
        sb.append(days);
        sb.append(" Days ");
        sb.append(hours);
        sb.append(" Hours ");
        sb.append(minutes);
        sb.append(" Minutes ");
        sb.append(seconds);
        sb.append(" Seconds");

        return(sb.toString());
    }

Uhm... how many milliseconds are in a second? And in a minute? Division is not that hard.

int seconds = (int) ((milliseconds / 1000) % 60);
int minutes = (int) ((milliseconds / 1000) / 60);

Continue like that for hours, days, weeks, months, year, decades, whatever.

long time = 1536259;

return (new SimpleDateFormat("mm:ss:SSS")).format(new Date(time));

Prints:

25:36:259