Warming in the Arctic is larger than the global average. A primary reason for this Arctic Amplification is the albedo feedback. The contrasting albedo of sea ice and dark melted surface areas is the key component of albedo feedback. Cloud coverage over the changing surface and the response of the clouds to the changing surface conditions will modify the change in planetary albedo when sea ice melts. Space-based lidar measurements provide a unique opportunity for cloud measurements in the Arctic. The response of clouds to the changing sea ice concentration was directly observed. Based on CALIPSO satellite observations of cloud properties, this study found that cloud coverage in ice-free regions in the Arctic linearly increased with the area of ice-free water during the melt seasons in the past 10 years, while sea ice coverage varies significantly year-to-year. The observations suggest that when sea-ice retreats, cloud fraction of the ice-free region remains fixed at nearly 81%. The high cloud coverage over melted areas significantly reduces the albedo feedback. These results indicate that space-based lidar cloud and surface observations of the Arctic can help constrain and improve climate models.