Leaflet.js fitBounds with padding?

map.fitBounds(bounds, {padding: []}) should work. I suggest you to change padding to eg. [50, 50], maybe your padding values are too small.

Check out this JSFiddle example.

I came across this problem. As I understand the padding is controlled by the zoom. In my example all padding settings under 10 make no difference. As soon as the padding goes to 10 the map is zoomed out one level and there is padding. Furhter increasing the padding value has no influence, until it is so big that another zoom-out level is reached.

Leaflet only zooms between integer-value zoom levels by default. Past version 1.0.0, "fractional zooms" are available with the "zoomSnap" parameter:

var map = L.map('map', {
    zoomSnap: 0.1
});

This will allow smaller padding values to be visible, but will also affect scrollWheelZoom behavior.

FWI, you can also set a max zoom level to the map like so:

var map = L.mapbox.map('map', 'mapbox.emerald', {
    maxZoom: 16
});

this way you can avoid the map zooming in too much in case the markers are too close togther.