How Can You Wait Until Something Occurs?

While true do
if not game.Workspace:FindFirstChild("NameOfPart") then
--do something
end
wait(0.1)
end

workspace.ChildRemoved:Connect(function(Child)
    if Child.Name == "InstanceName" then
        -- Your code
    end
end)

If you have a reference to the part that is going to be destroyed, it is better to do:

local part = workspace.PartToBeDestroyed -- for example
part.AncestryChanged:Wait() -- this waits for AncestryChanged to fire with any arguments - if you're sure that the part's parents won't change, this is all you need (and it is more efficient than loops since you don't have code running 30 times a second). If the parent can change around with the part being destroyed, connect to the event:

local con -- connection
con = part.AncestryChanged:Connect(function(child, parent)
    if parent ~= nil then return end
    con:Disconnect()
    -- The part has been destroyed
end

Tracking the connection made by Connect like that is unnecessary if you're connecting to an event owned by an object that will be Destroyed, but in the case that part was only de-parented rather than Destroyed (I believe this happens if the server destroys an object - the client only deparents it), it guarantees that the event will be cleaned up (preventing a memory leak).