user2532030's answer is the correct and most simple answer.
I just want to add, that in the case, where the value of the determining cell is not suitable for a RegEx-match, I found the following syntax to work the same, only with numerical values, relations et.c.:
[Custom formula is]
=$B$2:$B = "Complete"
Range: A2:Z1000
If column 2 of any row (row 2 in script, but the leading $ means, this could be any row) textually equals "Complete", do X for the Range of the entire sheet (excluding header row (i.e. starting from A2 instead of A1)).
But obviously, this method allows also for numerical operations (even though this does not apply for op's question), like:
=$B$2:$B > $C$2:$C
So, do stuff, if the value of col B in any row is higher than col C value.
One last thing: Most likely, this applies only to me, but I was stupid enough to repeatedly forget to choose Custom formula is in the drop-down, leaving it at Text contains. Obviously, this won't float...