Transition when removing class with display: none

I have a list of divs, some of them are hidden through class: "not-updated" while others are visible.

.not-update{
            display: none
}

At a certain point, due to some AJAX calls, some of the hidden divs might show up, by removing the class: "not-updated".

However, I would like that they appear with a transition, similarly to what happens with .fadeTo("slow", 1).

Here is a jsfiddle that might help to understand better the situation. In this example, for simplification, it will only appear one div, but in reality it could be several of them and randomly.

Trials

As you will see, I tried this suggestion, without success:

.box{
    -webkit-transition: all 0.5s ease;
    -moz-transition: all 0.5s ease;
    -o-transition: all 0.5s ease;
    transition: all 0.5s ease;
}

This one also did not help:

$(this).removeClass('not-updated',1000);

Any idea of how to achieve it?