To put it another way, let's re-derive why things float in the first place.
Conservation of energy and the minimum energy principle
We know that there is this principle of "conservation of energy" which says that energy is a "stuff" kind of like salt or water or air. That requires maybe a little explanation: it is not a "stuff" in the usual sense that everyone agrees on how much of that stuff is contained in any given box; but it is a "stuff" in the sense that if the amount in the box increases or decreases, the amount outside of the box must decrease or increase respectively. Instead of calling such strange mathematical quantities "pseudo-stuff" or something else like that, we call them "conserved." It just means "if there is a change then it had to either come from or go to somewhere else."
Now the "energy picture" of physics is a little more detailed than just that; it says that if a force $\vec F$ acts on an object moving with velocity $\vec v$ then the scalar product $P = \vec F \cdot \vec v = F_x v_x + F_y v_y + F_z v_z,$ which is known as the "power produced by the force", tends to change that object's kinetic energy $K = \frac12 m v^2.$ The correct expression involves a sum-of-all-forces just like Newton's law $m ~ d\vec v/dt = \sum_i \vec F_i,$ and says $dK/dt = \sum_i P_i.$ In other words, a force producing a constant power on an object will increase its kinetic energy linearly with the time that it acts on it.
For some forces, we can define a "potential energy" $U,$ the technical expression is $\vec F = - \vec \nabla U.$ In such cases it turns out that the total change in kinetic energy $\Delta K = \int dt~\vec F\cdot\vec v$ becomes the path-independent difference $-\Delta U,$ in which case indeed this number $K + U,$ the "total energy", is conserved.
For other forces, energy is still conserved but we are not paying careful attention to where it is going. Friction and drag forces are a great example. Usually these oppose your direction of motion through a medium, so in the reference frame where that medium is stationary, you have $\vec F \propto -\vec v,$ and that is a magical relationship because it means that they always have negative power and rob energy from the system! Well the smallest $K$ can be is if $v=0$ and this means that drag forces tend to eventually bring you to rest somewhere; and the smallest $U$ can be is at a potential energy minimum and this means that drag forces tend to eventually bring you at rest at the minimum places of potential energy. (Control question: why is this argument not working for my coffee cup right now? It's on my desk, it's feeling frictional forces: why is it not on the floor where the potential energy is lower?)
Still we can use this as a great principle.
Buoyancy as a straightforward consequence.
Suppose I have a box of volume V underwater: does it sink or does it float? That is easy, look for the minimum potential energy. If I put it at the bottom of the ocean, we will say that this is $U=0$. Now if I raise it to a height $H$ relative to that, what happens? Well the obvious thing is that I have to put in the energy $m g H$ to lift the box. But what about the water? Well, a volume $V$ of water has to come from the box's new height $H$ and go all the way down to the height $0$ to compensate. So the total energy is $U = m g H - \rho V g H.$ And whether this is greater or lesser than 0 (corresponding to an increase or decrease, corresponding to sinking or floating) depends on whether $m > \rho V.$ Since $m/V$ is the average density of the box, we conclude: things more dense than water sink, things less dense than water float. This is also why a ship sinks if it has a hole in it or if its sides go under the water: then its decks start to fill up with water which makes it heavier and heavier as the water replaces the air pockets that kept it floating, eventually making it so heavy that it is more dense than water and it sinks.
How this solves your question
Notice that there is a very special circumstance, though, when the thing floats to the top of the surface. Our argument stops working. Our argument says that ships should entirely sit on the surface of the water; our experience says that they sink in a little bit, but hopefully not too much.
Well the problem is that you still need to bring a volume $V$ of water to the bottom of the ocean, but it does not all come from the height $H$! Once the box emerges from the surface, the water does not need to be subtracted from the top-side of the box in order to make room for the box; the rest of the water needs to instead be subtracted from the surface.
With a little bit of reasoning, you can work out the following general principle: cut an imaginary plane flush with the surface of the water, and look at how much of the box is underneath it: this volume is the "displaced volume" $V_D$. Then a box will float to the surface precisely until $V_D = m / \rho.$ So boats will therefore sink some characteristic depth into the water.
Now when the ice cube melts a little bit, there is not very much water, and certainly not enough to raise the water level to the needed characteristic depth. But eventually when the ice cube is nearly all the way melted, it's in a big sea of water and it should be floating. The question is: what is the cut-off point between these two extremes?